#ifndef __JK_LIST_H_
#define __JK_LIST_H_

#include "jk_base.h"
#include "jk_iterator.h"
#include "jk_traits.h"

JK_LIB_NAMESPACE_BEGIN

template <typename T>
class List;

template <typename T>
class ForwardIterator<List<T>>
{
public:
    typedef typename List<T>                            ContainerType;
    typedef typename ContainerType::node_type           node_type;
    typedef typename ContainerType::value_type          value_type;
    typedef typename ContainerType::value_type&         reference;
    typedef const typename ContainerType::value_type&   const_reference;
    typedef typename ContainerType::value_type*         pointer;
    typedef const typename ContainerType::value_type*   const_pointer;
    friend class ContainerType;

public:
    ForwardIterator()
        : container_(NULL)
        , curr_(NULL)
        , end_(NULL)
    {
    }

    explicit ForwardIterator(ContainerType& container)
        : container_(&container)
        , curr_(container.head_)
        , end_(container.tail_)
    {
    }

    ForwardIterator(const ForwardIterator<ContainerType>& it)
        : container_(it.container_)
        , curr_(it.curr_)
        , end_(it.end_)
    {
    }

// private:
//     ForwardIterator(ContainerType& container, node_type* curr)
//         : container_(&container)
//         , curr_(curr)
//         , end_(container.tail_)
//     {
//     }

public:
    bool IsValid()
    {
        return (container_ != NULL
            && curr_ != NULL
            && end_ != NULL
            && curr_ < end_);
    }

public:
    reference operator*()
    {
        assert(IsValid());
        return curr_;
    }

    ForwardIterator<ContainerType>& operator++()
    {
        assert(IsValid());
        curr_ = curr_->next_;
        return (*this);
    }

    ForwardIterator<ContainerType> operator++(int)
    {
        assert(container_ != NULL);
        ForwardIterator<ContainerType> temp = (*this);
        curr_ = curr_->next_;
        return temp;
    }

    ForwardIterator<ContainerType>& operator--()
    {
        assert(IsValid() && curr_->prev_ != NULL);
        curr_ =curr_->prev_;
        return (*this);
    }

    ForwardIterator<ContainerType> operator--()
    {
        assert(IsValid() && curr_->prev_ != NULL);
        ForwardIterator<ContainerType> temp = (*this);
        curr_ =curr_->prev_;
        return temp;
    }

    ForwardIterator<ContainerType>& operator=(const ForwardIterator<ContainerType>& it)
    {
        curr_ = it.curr_;
        end_ = it.end_;
        container_ = it->container_;
    }

    bool operator==(const ForwardIterator<ContainerType>& it) const
    {
        assert(IsValid());
        return (container_ == it.container_ 
            && curr_ == it.curr_
            && end_ == it.end_);
    }

    bool operator!=(const ForwardIterator<ContainerType>& it) const
    {
        return !((*this) == it);
    }

private:
    node_type*      curr_;
    node_type*      end_;
    ContainerType*  container_;
};

template <typename T>
struct ListNode
{
    typedef typename T              value_type;
    typedef ListNode<value_type>    node_type;
    typedef value_type&             reference;
    typedef const value_type&       const_reference;
    typedef value_type*             pointer;
    typedef const value_type*       const_pointer;

    explicit ListNode(const T& data = T())
        : prev_(NULL)
        , next_(NULL)
        , data_(data)
    {
    }

    ~ListNode()
    {
        prev_ = NULL;
        next_ = NULL;
    }

    node_type* prev_;
    node_type* next_;
    T data_;
};

template <typename T>
class List
{
public:
    typedef ListNode<T>                 node_type;
    typedef T                           value_type;
    typedef T&                          reference;
    typedef const T&                    const_reference;
    typedef T*                          pointer;
    typedef const T*                    const_pointer;
    typedef ForwardIterator<List<T>>    forward_iterator;
    typedef forward_iterator            iterator;
    friend class iterator;

public:
    List()
        : tail_(new node_type)
        , rtail_(new node_type)
    {
        rhead_ = tail_->prev_ = rtail_;
        head_ = tail_;
    }

    ~List()
    {
        while (head_ != NULL && head_ != tail_)
        {
            head_ = head_->next_;
            delete head_->prev_;
        }

        if (head_ != NULL)
            delete head_;

        if (tail_ != NULL)
            delete tail_;

        head_ = tail_ = NULL;
    }

public:
    void Append(const T& value)
    {
        node_type* node = new node_type(value);
        if (head_ == tail_)
        {
            head_ = node;
            node->prev_ = rtail_;
            rtail_->next_ = node;
        }
        else
        {
            node_type* temp = head_;
            while (temp->next_ != tail_)
                temp = temp->next_;

            temp->next_ = node;
            node->prev_ = temp;
        }

        rhead_ = node;
        node->next_ = tail_;
        tail_->prev_ = node;
        ++num_of_nodes_;
    }

    void Insert(int pos, const T& value)
    {
        assert(abs(pos) < num_of_nodes_);
        iterator iter;
        if (abs(pos) > num_of_nodes_ / 2)
        {
            if (pos > 0)
                pos = pos - num_of_nodes_;
            else
                pos = num_of_nodes_ + pos;
        }

        if (pos > 0)
        {
            iter = Begin();
            while (pos--)
                ++iter;
        }
        else
        {
            iter = End();
            while (pos++)
                --iter;
        }

        Insert(value, iter);
    }

    void Insert(const T& value, const iterator& pos)
    {
        assert(pos.container_ == this);
        assert(pos != End());
        
    }

    int GetNumOfElements()
    {
        return num_of_nodes_;
    }

    iterator Begin()
    {
        return iterator(this);
    }

    iterator End()
    {
        return iterator(this, tail_);
    }

private:
    node_type*  head_;
    node_type*  tail_;
    node_type*  rhead_;
    node_type*  rtail_;
    int         num_of_nodes_;
};


JK_LIB_NAMESPACE_END

#endif //!__JK_LIST_H_
